/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

//第一种解法:遍历递归
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null){
            return root;
        } else if(left != null){
            return left;
        } else {
            return right;
        }  
    }
}


//第二种解法:利用栈
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int len = stack1.size()-stack2.size();
        if(len > 0){
            while(len != 0){
                stack1.pop();
                len--;
            }
        }else if(len < 0){
            while(len != 0){
                stack2.pop();
                len++;
            }
        }
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            TreeNode node1 = stack1.pop();
            TreeNode node2 = stack2.pop();
            if(node1.val == node2.val)
            return node1;
        }
        return null; 
}
        boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
            if(root == null || node == null) return false;
            stack.push(root);
            if(root == node) return true;
            boolean flg = getPath(root.left,node,stack);
            if(flg) return true;
            flg = getPath(root.right,node,stack);
            if(flg) return true;
            stack.pop();
            return false;
    }
}
